#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


bool check(const char *p)
{
    while (*p)
        if (*p++ != '*') return false;

    return true;
}

bool isMatchhelper(const char *s, const char *p, const char *last, int index) {

  if (index > 100) {
      cout << s << " " << p << " " << index << endl;
      return false;
  }

    bool ans = false;
    if (!*s && !*p) return true;
    if (last && *last == '*' && *p == '\0' && *s)
	    return true;

    if (!*s && check(p)) return true;

	if (!*s || !*p) return false;

    if (*p == '?' ) {
    	return isMatchhelper(s+1, p+1, p, index+1);
    }

    if (*p == '*') {
         while(*s) {
             ans |= isMatchhelper(s, p+1, p, index+1);
             if (ans) return ans;
             s++;
          }
    }

    if (*s == *p) {return isMatchhelper(s+1, p+1,p, index+1);}
    if (*s != *p) return false;
 }

class Solution {
    public:
        bool isMatch(const char *s, const char *p) {
            int index = 0;  
            return isMatchhelper(s, p, NULL, index);
        }
};

//add more clean code from me still could not pass large test case
    bool isMatch(const char *s, const char *p) {
        if (!*s && !*p) return true;
        else if (!*s) {
            while(*p == '*') p++;
            return *p == '\0';
        } else if (!*p) {
            return false;
        }   

        if (*p == '?') return isMatch(s+1, p+1);
        else if (*p == '*') {
            int i = 0;
            do {
                if (isMatch(s+i, p+1))
                    return true;
                i++;
            } while(*(s+i));
            //BUG here need to check when the s get to the end;
            if (isMatch(s+i, p+1)) return true;
        } else {
            return (*p == *s) && isMatch(s+1, p+1);
        }   
        //BUG 
        return false;
    }   

// short code from github
    bool isMatch(const char* s, const char* p) {
        if (*s == '\0') {
            if (*p == '\0') return true;
            if (*p == '*') return isMatch(s,p+1);
            return false;
        }
        if (*p == '\0') return false;
        if (*p == '?' || *p == *s) return isMatch(s+1, p+1);
        if (*p=='*') return isMatch(s+1,p) || isMatch(s, p+1);
        return false;
    }
};



//best code from longway2008
bool isMatch(const char *str, const char *pat, bool hasStar=false) 
{
  if (!*pat) return !*str || hasStar;
  
  const char *s, *p;
  for (s = str, p = pat; *s; ++s, ++p) {
     if (*p == '*') 
        return isMatch(s, p+1, true);  
     else if ( *p != '?' && *s != *p) 
        return !hasStar ? false : isMatch(str+1, pat, hasStar);
  }
   
  while (*p == '*') ++p;
  return (!*p);      
}

//iterative code 
bool isMatch(const char *s, const char *p) {
   if (!p) return !s;
   if (!s) return !p;

   for (const char *star=NULL, *s_save=s; *s; ) { 
     // star是上一个*出现的位置；s_save+1是出现不匹配时，s应该回到的位置。

     if (*p == '*') {
        star = p++;
        s_save = s;
     } else if ( *p != '?' && *s != *p) {  // 不匹配
        if (!star) { // 没有*来做灵活匹配
           return false;
         } else {  // 有*， 回到star+1 和 s_save+1匹配

           p = star+1;
           s = ++s_save;
         }
     } else {  // 匹配时，p和s都前进到下一个
         s++;
         p++;
     }
   }

   while (*p == '*')  p++; // pattern结尾的*可以消耗掉

   return !*p;  // 看是否已经到p的末尾
}







int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;

    cout << mySolution.isMatch("aa","a") << endl;
    cout << mySolution.isMatch("aa","aa") << endl;
    cout << mySolution.isMatch("aaa","a") << endl;
    cout << mySolution.isMatch("aa","*") << endl;
    cout << mySolution.isMatch("aa","a*") << endl;
    cout << mySolution.isMatch("aa","?*") << endl;
    cout << mySolution.isMatch("aab","c*a*b") << endl;

    char *str = "aaabbaaaaaabbbaabbbbaabbbabbaaaaabbbbbbbaaabbbbaabaabbababaabaabbaaabbbbbabababbbbbbabaaaaababaabaaaaaabababbbababaababbabbaabababaababbbbaaaababbbabaabbbaaaababbaabababbbabaababbbbbbbabbbbabbaabbabab";
    char *str2 = "******bb*a*ba*****babbbb**bb*b*aa***a*b*aaaa***bbab*b*aa*bba**a*b**b**b**b*bab*bb*a**b*a**ab*b*aabb*a*b";

    cout << mySolution.isMatch(str, str2) << endl;
    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
